package com.shm.leetcode;

/**
 * 598. 范围求和 II
 * 给定一个初始元素全部为 0，大小为 m*n 的矩阵 M 以及在 M 上的一系列更新操作。
 *
 * 操作用二维数组表示，其中的每个操作用一个含有两个正整数 a 和 b 的数组表示，含义是将所有符合 0 <= i < a 以及 0 <= j < b 的元素 M[i][j] 的值都增加 1。
 *
 * 在执行给定的一系列操作后，你需要返回矩阵中含有最大整数的元素个数。
 *
 * 示例 1:
 *
 * 输入:
 * m = 3, n = 3
 * operations = [[2,2],[3,3]]
 * 输出: 4
 * 解释:
 * 初始状态, M =
 * [[0, 0, 0],
 *  [0, 0, 0],
 *  [0, 0, 0]]
 *
 * 执行完操作 [2,2] 后, M =
 * [[1, 1, 0],
 *  [1, 1, 0],
 *  [0, 0, 0]]
 *
 * 执行完操作 [3,3] 后, M =
 * [[2, 2, 1],
 *  [2, 2, 1],
 *  [1, 1, 1]]
 *
 * M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。
 * 注意:
 *
 * m 和 n 的范围是 [1,40000]。
 * a 的范围是 [1,m]，b 的范围是 [1,n]。
 * 操作数目不超过 10000。
 * @author SHM
 */
public class MaxCount {
    /**
     * 方法一：维护所有操作的交集
     * 思路与算法
     *
     * 对于每一次操作，给定 (a, b)(a,b)，我们会将矩阵中所有满足 0 \leq i < a0≤i<a 以及 0 \leq j < b0≤j<b 的位置 (i, j)(i,j) 全部加上 11。由于 a, ba,b 均为正整数，那么 (0, 0)(0,0) 总是满足上述条件，并且最终位置 (0, 0)(0,0) 的值就等于操作的次数。
     *
     * 因此，我们的任务即为找出矩阵中所有满足要求的次数恰好等于操作次数的位置。假设操作次数为 kk，那么 (i, j)(i,j) 需要满足：
     *
     * \begin{cases} 0 \leq i < a_0, 0 \leq i < a_1, \cdots, 0 \leq i < a_{k-1} \\ 0 \leq j < b_0, 0 \leq j < b_1, \cdots, 0 \leq j < b_{k-1} \\ \end{cases}
     * {
     * 0≤i<a
     * 0
     * ​
     *  ,0≤i<a
     * 1
     * ​
     *  ,⋯,0≤i<a
     * k−1
     * ​
     *
     * 0≤j<b
     * 0
     * ​
     *  ,0≤j<b
     * 1
     * ​
     *  ,⋯,0≤j<b
     * k−1
     * ​
     *
     * ​
     *
     *
     * 等价于：
     *
     * \begin{cases}\tag{1} 0 \leq i < \min\limits_k a \\ 0 \leq j < \min\limits_k b \end{cases}
     * ⎩
     * ⎪
     * ⎨
     * ⎪
     * ⎧
     * ​
     *
     * 0≤i<
     * k
     * min
     * ​
     *  a
     * 0≤j<
     * k
     * min
     * ​
     *  b
     * ​
     *  (1)
     *
     * 这样一来，我们只需要求出 aa 和 bb 中的最小值，分别记为 \min\limits_k a
     * k
     * min
     * ​
     *  a 以及 \min\limits_k b
     * k
     * min
     * ​
     *  b，那么满足 (1)(1) 式的 (i, j)(i,j) 一共有 \min\limits_k a \times \min\limits_k b
     * k
     * min
     * ​
     *  a×
     * k
     * min
     * ​
     *  b 对。
     *
     *  复杂度分析
     *
     * 时间复杂度：O(k)O(k)，其中 kk 是数组 \textit{ops}ops 的长度。
     *
     * 空间复杂度：O(1)O(1)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/range-addition-ii/solution/fan-wei-qiu-he-ii-by-leetcode-solution-kcxq/
     * @param m
     * @param n
     * @param ops
     * @return
     */
    public int maxCount(int m, int n, int[][] ops) {
        int minA = m,minB = n;
        for (int[] op : ops) {
            minA=Math.min(minA,op[0]);
            minB=Math.min(minB,op[1]);
        }
        return minA*minB;
    }
}
